/**
 * Created with Intellij IDEA.
 * Description:
 * User:Lenovo
 * Date:2025-01-04
 * Time:11:12
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return Build(preorder,inorder,0,0,inorder.length-1);
    }
    public TreeNode Build(int[] preorder,int[] inorder,int preIndex,int pre,int end){
        if(preIndex>end){
            return null;
        }
        int index = find(inorder,pre,end,preorder[preIndex]);
        if(index==-1){
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre]);
        preIndex++;
        root.left = Build(preorder,inorder,preIndex,pre,index);
        root.right = Build(preorder,inorder,preIndex,index+1,end);
        return root;
    }
    public int find(int[] inorder,int pre,int end,int key){
        for(int i=pre;i<=end;i++){
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
}
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;TreeNode() {}
      TreeNode(int val) {
          this.val = val;
      }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
      }
    public static void main(String[] args) {
          Solution solution = new Solution();
          int[] preorder={3,9,20,15,7};
          int[] inorder={9,3,15,20,7};
          TreeNode root = solution.buildTree(preorder,inorder);
          System.out.println(root.val);
    }
}
